package com.jacky.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 三数之和_15 {
    public List<List<Integer>> threeSum(int[] nums) {
        //定义好返回值
        List<List<Integer>> res = new ArrayList();
        //校验入参
        if (nums == null || nums.length < 3) return res;
        //对整型数组从小到大排序，java这个方法用的是快排
        Arrays.sort(nums);
        //获得数组的长度
        int length = nums.length;
        //开始遍历排序好的数组
        for (int i = 0; i < length; i++) {
            //左指针等于i+1
            int left = i + 1;
            //右指针指向数组最后一个元素
            int right = length - 1;
            //若 nums[i]>0，因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果
            if (nums[i] > 0) break;
            //对于遍历到的重复元素：跳过，避免出现重复解
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            //当left>=right的时候，i才会继续向后遍历，同时重置左指针和右指针
            while (left < right) {
                int temp = nums[i] + nums[left] + nums[right];
                //若和小于 0，说明 nums[left] 太小，left右移
                if (temp < 0) {
                    left++;
                    //若大于0，说明nums[right]太大，right左移
                } else if (temp > 0) {
                    right--;
                    //等于目标值0，就放到List里面
                } else {
                    List<Integer> list = new ArrayList();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    //判断左指针下一个值是否和当前值一样，如果是就要跳过
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    //判断右指针下一个值是否和当前值一样，如果是就要跳过
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    //对于值等于0的情况，要左++，右--
                    left++;
                    right--;
                }
            }
        }
        return res;
    }

}
